ATM (Asynchronous Transfer Mode) is a known connection-oriented packet-switching technique, which has been selected by the international organization for telecommunications standardization ITU-T as the target transfer mode solution for implementing a broadband multimedia network (B-ISDN). In these networks many traffic sources are bursty, whereby the transmission capacity required at some moment is high and the capacity required at another moment is low. Bursts may be described as a phenomenon whereby a set of cells (a burst) arrives at short intervals and the following set (burst) arrives after a relatively long time. Since different connections need different capacities and the need varies quickly, statistical multiplexing is used in an ATM-based network. The statistical characteristics of bursty traffic sources are utilized in statistical multiplexing: when a large set of traffic sources are combined, the combined traffic behaves in a more stable manner than the individual sources, and although the transmission speed of an individual traffic source varies, the combined transmission speed of mutually independent individual traffic sources is almost constant. By using statistical multiplexing, it is possible to serve more connections with the same resources, i.e. the utilization rate of the network can be increased.
In spite of statistical multiplexing, congestion and overload will still occur in the network, caused both by unpredictable statistical variations in the traffic and by failure situations occurring in the network. Since it is impossible to know with sufficient accuracy the services to be provided, the volume of traffic brought about by the services, and the exact characteristics of the traffic sources, the occurrence of congestion is unavoidable in a network. The purpose of traffic and congestion control is to protect the network and the user so that the desired quality of a service is achieved.
Traffic control is intended to prevent the occurrence of congestion situations, while congestion control reacts to congestion situations detected in the network. From the point of view of the quality of service (QoS), most significant are the traffic control functions which try to prevent congestion situations in advance, of which Connection Admission Control (CAC) is the most important preventive traffic control method. CAC is defined as the set of procedures taken by the network during the call (virtual connection) set-up phase, or during the call re-negotiation phase, to determine whether a connection request can be accepted or rejected. CAC accepts a connection only when sufficient resources are available at each successive link in the circuit, and when the new connection will not adversely affect the quality of service of existing connections.
Several different methods of implementing CAC are known. These methods are based either on traffic parameters stated by the user or on traffic measurements taking place in the network element. It is possible to estimate the quality of service or the capacity requirement which can be expected according to traffic parameters either with the aid of pre-computed tables as in methods termed “indirect” or by computing in real time based on traffic parameters informed in the connection request, as is done in methods termed “direct”.
Various requirements, at least some of which are contradictory to one another, must be set for the CAC algorithms determining the acceptability of a connection request. A CAC algorithm should, for example, be as generic as possible in the sense of its applicability to the management of traffic sources of a wide number of different types. The algorithm must also be simple enough, for example, to be applied in real-time so that it will not form a bottle-neck restricting the call processing capacity of the switch. On the other hand, the algorithm should be very efficient in order to utilize the network resources optimally and to guarantee fair treatment of connections of different types.
ATM Forum has specified five different service categories which relate traffic characteristics and the quality of service (QoS) requirements to network behavior. These service classes are: constant bit rate (CBR), real-time variable bit rate (rt-VBR), non-real time variable bit rate (nrt-VBR), available bit rate (ABR), and unspecified bit rate (UBR). As each class represents connections which have essentially homogeneous traffic pattern characteristics and QoS requirements, it is easier to implement the CAC algorithm and to guarantee the QoS requirements of the existing connections if the capacities of links between two neighbouring network elements (switches) are divided into several virtual paths. For example, it would be very difficult to guarantee the QoS requirements of CBR traffic if UBR traffic shared the same logical queues with it. However, by dividing the available capacity between a plurality of virtual paths, each virtual path can accommodate the traffic of only one service class.
Thus, in practice there can be numerous (semi-permanent) virtual paths between two neighbouring network elements (the maximum number allowed is 64000). FIG. 1 illustrates this situation in an ATM network. The virtual paths between two neighbouring switches are shown as dashed lines.
Consequently, the network element includes means for choosing the virtual path from the set of alternative virtual paths heading to the desired destination. FIG. 2 is a functional block diagram illustrating one possible implementation of the virtual path selection in a switch. When a connection request arrives at the switch, a connection control block CC supplies the desired input data to the connection admission control and commands a selection block SB to select a candidate virtual path for the request. A connection request received includes typically at least the service class required and the traffic parameters describing the source, as shown in the figure. The selection block selects a virtual path and supplies the identifier of this virtual path to the connection admission control. The routing hierarchy is stored in the resources block RB and the selection block uses this hierarchy to determine the group of available virtual paths.
Using the input information the connection admission control then decides whether this virtual path can accommodate the connection requested. As a result, CAC returns a “yes” or “no” answer to the selection block. If CAC rejects the selected virtual path, the selection block selects a new candidate and supplies its identifier to CAC. In this way the selection block selects virtual paths until a virtual path is found that can accommodate the connection or until all the virtual paths have been tested and rejected. In the latter case, the connection request is rejected.
A straightforward selection method is to try each virtual path in consecutive order. In this method, however, the time required to find an acceptable virtual path may be rather lengthy. Thus, the problem in this kind of an environment is how to select a virtual path which CAC will accept with the minimum number of trials.
The same problem arises when a virtual channel is sought for connections (such as AAL2 connections) that can share one virtual channel (i.e. one ATM cell). In other words, free capacity can be searched for from entities on different hierarchical levels. In the following, the entities tested in order to find one with enough free capacity are called (logical) transmission resources. Thus, a (logical) transmission resource can in this context be a virtual path or a virtual channel.